/*
 * @lc app=leetcode.cn id=332 lang=cpp
 *
 * [332] 重新安排行程
 *
 * https://leetcode-cn.com/problems/reconstruct-itinerary/description/
 *
 * algorithms
 * Hard (46.08%)
 * Likes:    558
 * Dislikes: 0
 * Total Accepted:    54.5K
 * Total Submissions: 118.1K
 * Testcase Example:  '[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]'
 *
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi]
 * 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 * 
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK
 * 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 * 
 * 
 * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 * 
 * 
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
 * 输出：["JFK","MUC","LHR","SFO","SJC"]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：tickets =
 * [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
 * 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
 * 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * tickets[i].length == 2
 * fromi.length == 3
 * toi.length == 3
 * fromi 和 toi 由大写英文字母组成
 * fromi != toi
 * 
 * 
 */

// @lc code=start
class Solution {
// private:
//     bool backtracking(unordered_map<string, map<string, int>>& targets, int ticketNum, vector<string>& res) {
//         if(res.size() == ticketNum + 1) {
//             return true;
//         }

//         // for(pair<const string, int>& target : targets[res[res.size()-1]]) {
//         for(pair<const string, int>& target : targets[res.back()]) {
//             // if(target.second > 0) {
//             //     res.push_back(target.first);
//             //     target.second--;
//             //     if (backtracking(targets, ticketNum, res)) return true;
//             //     target.second++;
//             //     res.pop_back();
//             // }
//             if(target.second == 0) continue;
//                 res.push_back(target.first);
//                 target.second--;
//                 if (backtracking(targets, ticketNum, res)) return true;
//                 target.second++;
//                 res.pop_back();       
//         }

//         return false;
//     }
// public:
//     vector<string> findItinerary(vector<vector<string>>& tickets) {
//         vector<string> res;
//         unordered_map<string, map<string, int>> targets;
//         // <出发地, <目的地, 航班次数>>
//         for(vector<string> vec : tickets) {
//             targets[vec[0]][vec[1]]++;
//         }
//         res.push_back("JFK");
//         backtracking(targets, tickets.size(), res);
//         return res;

//     }

private:
    unordered_map<string, map<string, int>> targets;
    bool backtracking(int num, vector<string>& res) {
        if(num+1 == res.size()) return true;

        for(pair<const string, int>& target : targets[res.back()]) {
            if(target.second == 0) continue;
            res.push_back(target.first);
            target.second--;

            if(backtracking(num, res)) return true;

            target.second++;
            res.pop_back();
        }
        return false;
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> res;
        for(vector<string> vec : tickets) {
            targets[vec[0]][vec[1]]++;
        }
        for(auto target : targets) {
            cout<<target.first<<":"<<endl;
            for(auto tar : target.second){
                cout<<tar.first<<" "<< tar.second<<" ";
            }
            cout<<endl;
        }
        res.push_back("JFK");
        backtracking(tickets.size(), res);
        for(int i = 0; i < res.size(); i++) {
            cout<<res[i]<<" ";
        }
        return res;
    }


};
// @lc code=end

